package com.example;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.stream.IntStream;

import static java.lang.Math.max;


/**
 * Created by gerrie on 19/03/2019.
 */

public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        LinkedList<Integer> maxIndex = new LinkedList<>();
        ArrayList<Integer> result = new ArrayList<>();
        if(num ==null || num.length == 0 || size< 1)
            return result;
        for (int i = 0; i < num.length ; i++) {
            while(!maxIndex.isEmpty()) {
                int maxIdx = maxIndex.getLast();
                if (num[i] > num[maxIdx]) {
                    maxIndex.removeLast();
                }else
                    break;
            }
            maxIndex.addLast(i);
            if(i<size - 1){
                continue;
            }
            if(!maxIndex.isEmpty() && maxIndex.getFirst() <= (i-size))
                maxIndex.removeFirst();
            result.add(num[maxIndex.getFirst()]);
        }
        return result;
    }
    //02:41
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        //check
        if(matrix==null || matrix.length==0 || rows< 1 || cols <1
                || str==null ||str.length ==0)
            return false;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                boolean[] hits = new boolean[16];
                if(hasPathCore(matrix, rows, cols, str, 0, i, j, hits))
                    return true;
            }
        }
        return false;
    }

    public boolean hasPathCore(char []matrix, int rows, int cols, char[]str, int curStr, int x, int y, boolean[]hits){
        //
        if(x<0 || x >= cols || y < 0 || y >= rows)
            return false;
        boolean hit = false;
        char c = matrix[y*cols + x];
        if(c != str[curStr])
            return false;
        if(hits[y * cols + x])
            return false;
        if(curStr == str.length - 1) {
            hits[y * cols + x] = true;
            return true;
        }
        hit |= this.hasPathCore(matrix, rows, cols, str, curStr+1, x + 1, y, hits);
        hit |= this.hasPathCore(matrix, rows, cols, str, curStr+1, x - 1, y, hits);
        hit |= this.hasPathCore(matrix, rows, cols, str, curStr+1, x, y + 1, hits);
        hit |= this.hasPathCore(matrix, rows, cols, str, curStr+1, x, y - 1, hits);
        return hit;
    }


    public int movingCount(int threshold, int rows, int cols)
    {
        if(threshold<1 || rows < 1|| cols < 1)
            return 0;
        return 0;
    }

    public void movingCore(int thred, int rows, int cols){

    }

    public List<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        int maxHeap[] = new int[k];
        for(int i = 0;i< k;i ++){
            maxHeap[i] = input[i];
        }
        buildHeap(maxHeap, k);
        for(int i = k; i< input.length;i ++ ){
            if(input[i] > maxHeap[0])
                continue;
            maxHeap[0] = maxHeap[maxHeap.length - 1] ;
            maxHeap[maxHeap.length - 1] = input[i];
            buildHeap(maxHeap, maxHeap.length);
        }
//        ArrayList<Integer> result =  Arrays.asList(maxHeap);

//        List<Integer> result  = Arrays.stream( maxHeap ).boxed().collect( Collectors.toList() );
        ArrayList<Integer> result = new ArrayList<>();
        for (int v :
                maxHeap) {
            result.add(v);
        }
        return result;
    }

    private void buildHeap(int []input, int length){
        int index = (length - 1) /2;
        while(index >=0){
            int p = input[index];
            int l = index * 2 + 1;
            int max = l;
            if(index * 2 + 2 < length){
                int r = index * 2 + 2;
                if(input[r] > input[l])
                    max = r;
            }
            if(input[max] > p){
                input[index] = input[max];
                input[max] = p;
            }
            index -=1;
        }
    }


    public boolean isAnagram(String s, String t) {
        char[] cs = s.toCharArray();
        char[] ct = t.toCharArray();
        int [] buffer = new int[256];
        for (int i = 0; i < cs.length; i++) {
            int c = cs[i];
            buffer[c]+=1;
        }
        for (int i = 0; i < ct.length; i++) {
            buffer[ct[i]] -= 1;
        }
        int sum = Arrays.stream(buffer).reduce(0,(a,b)->a+b);
//        int reduce = Arrays.asList(buffer).stream().reduce(0, (a, b) -> a + b); //  错误的写法
        if(sum ==0)
            return true;
        else
            return false;
    }

    /**
     * 有问题。见我的leetcode提交修复版。
     */
    public boolean isIsomorphic(String s, String t) {
        if(s.length() != t.length())
            return false;
        char []ss = s.toCharArray();
        char []st = t.toCharArray();
        int []last_pos = new int[256];
        int []last_pos_t = new int[256];
        for (int i = 0; i < ss.length; i++) {
            char cs = ss[i];
            char ct = st[i];
            if(last_pos[cs] != last_pos_t[ct])
                return false;
            last_pos[cs] = i;
            last_pos_t[ct] = i;
        }
        return true;
    }

    public ArrayList<String> restoreIpAddresses(String s) {
        ArrayList<String> result = new ArrayList<>();
        ArrayList<String> store = new ArrayList<>();
        helper(s, result, 0, 0, "");
        return result;
    }

    public void helper(String s, ArrayList<String> result, int pos, int index, String prefix){
        if(index == 3){
            //  abc
            if((s.length() - pos)<=3){
                String s4 = s.substring(pos,s.length());
            }
        }
        if(s.charAt(pos) == '0')
            return;
        if(index == 0){
            helper(s, result, pos + 1, 2, prefix + s.substring(pos, pos + 1));
            helper(s, result, pos + 2, 2, prefix + s.substring(pos, pos + 2));
            helper(s, result, pos + 3, 2, prefix + s.substring(pos, pos + 3));
        }

    }

    public static boolean isValid(String s){
        if(s.length()<=0 || s.length() > 3)
            return false;
        int i = Integer.parseInt(s);
        if(String.valueOf(i).length() != s.length())
            return false;
        if (0 <= i && i < 256)
            return true;
        return false;
    }

    public String rotateString(String s, int offset){
        StringBuilder sb = new StringBuilder(s);
        sb.substring(0, s.length() - offset);
        return null;
    }

    /** 要记太多api， 正确写法应该是 s.toCharArray(),
     */
    public void reverse(StringBuffer sb, int start, int end){
        while(start < end){
            char tmp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
        }
    }

    public int candy(int[] ratings) {
        int num[] = new int[ratings.length];
        for (int i = 0; i < ratings.length - 1; i++) {
            if(ratings[i] < ratings[i + 1])
                num[i+1] = num[i] + 1;
        }
        for (int i = ratings.length - 1; i > 1; i++) {
            if(ratings[i - 1] > ratings[i] && num[i-1] < num[i])
                num[i-1] = num[i] + 1;
        }
        int sum = 0;
        for(int n : num)
            sum += n;
        return sum;
    }
    public int longestCommonSubstring(String A, String B) {
        // write your code here
        char []as = A.toCharArray();
        char []bs = B.toCharArray();
        if(as.length == 0 || bs.length == 0)
            return 0;
        int f[][] = new int[A.length() + 1][B.length() + 1];
        int max = 0;
        for (int i = 0; i < as.length ; i++) {
            for (int j = 0; j < bs.length; j++) {
                int fi = i + 1, fj = j+1;
                if(as[i] == bs[j]){
                    if(i>0 &&j > 0 && as[i-1]== bs[j-1]){
                        f[fi][fj] = f[fi-1][fj-1] + 1;
                    }else
                        f[fi][fj] = 1;
                    max = max(f[fi][fj], max);
                }else{
                    f[fi][fj] = 0;
                    //f[fi][fj] = max(f[fi -1][fj], f[fi][fj-1]);
                }

            }
        }
        return max;
    }

    public double Power(double base, int exponent) {
        int ret = 1;
        IntStream.range(0, exponent).forEach(i-> {
            System.out.println(i);
//            ret = ret * base;
        });
        return ret;
    }

    public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> ret = new ArrayList<Integer>();
        if(matrix.length == 0)
            return ret;
        boolean [][] mask = new boolean[matrix.length][matrix[0].length];
        int [][]dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        //int []dir = {1, 0};
        int dirIndex = 0;
        int []pos = {0, 0};
        while(true){
            ret.add(matrix[pos[1]][pos[0]]);
            mask[pos[1]][pos[0]] = true;
            System.out.println(matrix[pos[1]][pos[0]]);

            int []dir = dirs[dirIndex];
            int ny = pos[1] + dir[1];
            int nx = pos[0] + dir[0];
            if( (nx > (matrix[0].length - 1) )
                    || (ny > (matrix.length - 1))
                    || mask[ny][nx]){//mask[pos[1]][pos[0]]
                dirIndex = (dirIndex + 1) % 4;
            }
            dir = dirs[dirIndex];
            pos[0] += dir[0];
            pos[1] += dir[1];
            if(ret.size() == (matrix.length * matrix[0].length))
                break;
        }
        return ret;
    }

    public int FirstNotRepeatingChar(String str) {
        char []arr = str.toCharArray();
        int pos[] = new int[256];
        int cur = 0;
        for(int i =0; i < arr.length; i++){
            char c = arr[i];
            if(pos[(int)c] == 0){
                pos[(int)c] = i;
            }else{
                pos[(int)c] = -1;
            }
        }
        int min = 100000;
        for(int p: pos){
            if(p!=0 && p!= -1) {
                min = p < min ? p : min;
                System.out.println(p);
            }
        }
        if(min == 100000)
            return -1;
        return min;
    }
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }
    }

    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        LinkedList<TreeNode> current = new LinkedList<>();
        LinkedList<TreeNode> next = new LinkedList<>();
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if(pRoot==null)
            return result;
        current.push(pRoot);
        int layer = 1;
        while(current.size()!=0 && next.size()!=0){
            ArrayList<Integer> currentPrint = new ArrayList<>();
            while(current.size()!=0){
                TreeNode node = current.pop();
                if(node==null)continue;
                currentPrint.add(node.val);
                if(layer % 2 == 1){
                    if(node.left!=null) next.push(node.left);
                    if(node.right!=null) next.push(node.right);
                }else{
                    if(node.right!=null) next.push(node.right);
                    if(node.left!=null) next.push(node.left);
                }
            }
            current = next;
            next = new LinkedList<>();
            layer ++;
            result.add(currentPrint);
        }
        return result;
    }

    String Serialize(TreeNode root) {
        return "";
    }

    void dfs(TreeNode node, StringBuilder sb){
        if(node==null) {
            sb.append('#');
            return;
        }
        sb.append(node.val).append(",");
        //do
//        dfs(node.left);
//        dfs(node.right);
    }

/*    TreeNode Deserialize(String str) {

        String []nodes= str.split(",");
        if(nodes.length == 0)
            return null;
        TreeNode []tr_nodes = new TreeNode[nodes.length];
        for(int i = 1; i<nodes.length ; i ++){
            if(nodes[i].equals("#"))
                continue;
            int value = Integer.valueOf(node[i]);
            tr_nodes[i] = new TreeNode(value);
            TreeNode parent = tr_nodes[(i-1) /2];
            if(i%2==1)
                tr_nodes[i] = parent.left;
            else
                tr_nodes[i] = parent.right;
        }
        return tr_nodes[0];
    }*/
public List<Integer> topKFrequent_gerrie(int[] nums, int k) {
    HashMap<Integer, Integer> count = new HashMap<>();
    //可以直接count.put(int , int )吗？
    for(int num : nums){
        if(!count.containsKey(num))
            count.put(num, 0);
        count.put(num, count.get(num) + 1);
    }
    List<Integer> result = new ArrayList<>();
    //how to sort hashmap by value?
    //方法一、构建最小堆. 如何指定大小和小顶大顶？
    PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>();
    //如何遍历Hashmap?
/*    for(Map.Entry<Integer, Integer> entry: count){
        int num = entry.getKey();
        int value = entry.getValue();
        //队头是顶还是队尾是顶？
        if(queue.size() < k || queue.peek().getValue() < value){
            queue.offer(entry);
        }
    }
    //如何从小顶堆的末尾开始取？小顶堆不是有序的。。。只能翻转。。
    while(queue.size()!=0){
        result.add(queue.poll().getValues());
    }*/
    //todo reverse result..
    return result;
}
    class KeyValue{
        Integer key;
        Integer value;
        public KeyValue(Integer key,Integer value) {
            this.key=key;
            this.value=value;
        }
    }
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++) {
            if(map.containsKey(nums[i])) {
                map.put(nums[i],map.get(nums[i])+1);
            } else {
                map.put(nums[i],1);
            }
        }
        Iterator iter = map.entrySet().iterator();
        Queue<KeyValue> queue = new PriorityQueue<>(k,new Comparator<KeyValue>() {
            public int compare(KeyValue value1,KeyValue value2) {
                return value1.value-value2.value;
            }
        });
        int cnt=0;
        while(iter.hasNext()) { //对hashmap中元组遍历
            Map.Entry entry = (Map.Entry) iter.next();
            KeyValue tmp = new KeyValue((Integer) entry.getKey(),(Integer) entry.getValue());
            if(cnt<k) { //k大小优先队列
                queue.add(tmp);
            } else if(tmp.value>queue.peek().value) {   //比堆顶大，替换堆顶
                queue.poll();
                queue.add(tmp);
            }
            cnt++;
        }
        List<Integer> ret = new ArrayList<>();
        for(int i=0;i<k;i++) {
            ret.add(0,queue.poll().key);
        }
        return ret;
    }


    public void mySqrt(){

    }
}